Definition

Let Γ=(N,(Si)i∈N,(ui)i∈N)\Gamma = (N, (S^i)_{i \in N}, (u^i)_{i \in N}) be a finite NN-person game in strategic normal form, with NN denoting the set of players, SiS^i the set of strategies, ui:∏i∈NSi→ℝu^i: \prod_{i \in N} S^i \to \mathbb{R} is player ii's payoff function. Generic element of SS is s=(si)i∈Ns = (s^i)_{i \in N}, s−i=(si′)i′≠is^{-i} = (s^{i'})_{i' \neq i} is strategy combination of all players except ii.

A probability distribution ψ\psi on SS is a correlated equilibrium of Γ\Gamma if, ∀i∈N\forall i \in N, ∀j∈Si\forall j \in S^i, ∀k∈Si\forall k \in S^i, we have

∑s∈S:si=jψ(s)[ui(k,,s−i)−ui(s)]≤0\sum_{s \in S: s^i = j} \psi(s) [u^i(k,,s^{-i}) - u^i(s)] \leq 0

Define a correlated ϵ\epsilon-equilbrium if the right-hand side above is replaced by ϵ\epsilon.

Definition (correlated equilibrium and correlation device)

A (correlated) equilibrium of a given normal form game GG is a pair of

  1. strategy profile f=(f1,f2)f = (f_1, f_2), fi∈Γif_i \in \Gamma_i, i=1,2i = 1,2
  2. correlation device DD such that the strategy profile ff is a NE.
u1(f1,f2)≥u1(f1′,f2)∀f1′∈Γ1u1(f1,f2)≥u2(f1,f2′)∀f2′∈Γ2 \begin{aligned} u_1(f_1, f_2) & \geq u_1(f_1',f_2) \quad \forall f_1' \in \Gamma_1 \\ u_1(f_1, f_2) & \geq u_2(f_1,f_2') \quad \forall f_2' \in \Gamma_2 \end{aligned}

Nash equilibria

Every Nash equilibrium is a correlated equilibrium, the special case where ψ\psi is a product measure i.e. the play of different players is independent.

Definition (strategy vector as Nash equilibrium)

A probability distribution pp over the set of action vectors SS is a correlated equilibrium if the strategy vector τ∗\tau^* is a Nash equilibrium of the game Γ∗(p)\Gamma^*(p). In other words, for every player i∈Ni \in N,

∑s−i∈S−ip(si,s−i)ui(si,s−i)≥∑s−i∈S−ip(si,s−i)ui(si′,s−i)∀si,si′∈S\sum_{s_{-i} \in S_{-i}} p(s_i, s_{-i}) u_i(s_i, s_{-i}) \geq \sum_{s_{-i} \in S_{-i}} p(s_i, s_{-i}) u_i(s_i', s_{-i}) \quad \forall s_i, s_i' \in S

Strategy vector σ\sigma induces probability distribution pσp_\sigma over the set of action vectors SS,

pσ(s1,...,sn):=σ1(s1)×σ2(s2)×...×σn(sn)p_\sigma(s_1,...,s_n) := \sigma_1(s_1) \times \sigma_2(s_2) \times ... \times \sigma_n(s_n)

Theorem

For every Nash equilibrium σ∗\sigma^*, the probability distribution pσ∗p_{\sigma^*} is a correlated equilibrium.

convex hull of Nash equilibria

The convex hull of the set of Nash equilibria is the set

conv⁡{pσ∗:σ∗ is a Nash equilibrium}⊆Δ(S)\operatorname{conv}\{ p_{\sigma^*} : \sigma^* \text{ is a Nash equilibrium} \} \subseteq \Delta(S)

(where Δ(S)\Delta(S) is a simplex)

Corollary

It follows from the above theorem and Nash equilibrium#Corollary (perfect equilibrium as Nash equilibrium) that every finite strategic-form game has a correlated equilibrium.

Theorem

Set of correlated equilibria of a finite game is convex and compact.

Notes

Efficient algorithms such as simplex algorithm exist to calculate extreme points of polytope such as the simplex algorithm

Intuition of correlated equilibrium: assume that, before the game is played, each player receives a private signal (which does not affect the payoffs). The play may then choose his action in the game depending on this signal.

Consider: game of chicken

See also

References

  1. Hart S, Mas-Colell A. A Simple Adaptive Procedure Leading to Correlated Equilibrium. Econometrica, 2000; 68(5): 1127-1150. https://doi.org/10.1111/1468-0262.00153
  2. M. Maschler, E. Solan, and Shmuel Zamir, Game Theory, Cambridge University Press, 2013, pp. 307-308.
  3. https://en.wikipedia.org/wiki/Correlated_equilibrium